Kraft 不等式：信息论与编码理论中的一个基本条件，用来判断（或保证）一组码字长度能否对应某个前缀码（prefix code）或瞬时码（instantaneous code）。对字母表大小为 \(D\) 的编码，若码字长度为 \(l_1,l_2,\dots,l_n\)，则必须满足
\[
\sum_{i=1}^{n} D^{-l_i} \le 1
\]
在二进制情况下（\(D=2\)），就是 \(\sum 2^{-l_i}\le 1\)。常用于构造与分析最优编码（如 Huffman 编码）并与熵界联系起来。
/kræft ɪnˈikwɑːləti/
The Kraft inequality tells us whether a set of code lengths can form a prefix code.
Kraft 不等式告诉我们一组码长是否能够构成前缀码。
Using the Kraft inequality, we can design a binary prefix code whose lengths match the desired probabilities, which is a key step in proving bounds related to entropy.
利用 Kraft 不等式，我们可以设计一个二进制前缀码，使码长与目标概率相匹配，这也是证明与熵相关界限的关键步骤。
“Kraft inequality”得名于美国数学家/信息论学者 Leon G. Kraft，他在 1949 年的研究中提出了这一关于码长可实现性的条件；相关的推广与等价形式也常与 McMillan 的结果并称（Kraft–McMillan 不等式）。“inequality”来自拉丁语系词根，表示“不等式/不等关系”。
Select Language